package Graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _399EvaluateDivision {
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        Map<String, Map<String, Double>> map = new HashMap<>();
        for (int i = 0; i < equations.length; i++) {
            String[] eq = equations[i];
            if (!map.containsKey(eq[0])) map.put(eq[0], new HashMap<>());
            if (!map.containsKey(eq[1])) map.put(eq[1], new HashMap<>());
            map.get(eq[0]).put(eq[1], values[i]);
            map.get(eq[1]).put(eq[0], 1 / values[i]);
        }
        double[] res = new double[queries.length];
        Set<String> visit = new HashSet<>();
        for (int i = 0; i < queries.length; i++) {
            res[i] = helper(1, map, queries[i][0], queries[i][1], visit);
        }
        return res;
    }
    private double helper(double value, Map<String, Map<String, Double>> map, String start, String end, Set<String> set) {
        if (!map.containsKey(start) || set.contains(start)) return -1;
        if (end.equals(start)) return value;
        set.add(start);
        double res = -1;
        for (String str : map.get(start).keySet()) {
            res = helper(value * map.get(start).get(str), map, str, end, set);
            if (res != -1) break;
        }
        set.remove(start);
        return res;
    }
}
